Di sempadan Mexico–Amerika Syarikat, dua lelaki dalam sut hitam, Agen K dan Ejen D, mengganggu rondaan sempadan, menangkap salah seorang lelaki yang cuba menyeberangi sempadan, yang sebenarnya adalah makhluk luar angkasa. K terpaksa menembaknya apabila ia cuba menyerang peronda sempadan, dan D memutuskan sudah tiba masanya untuk bersara.

NYPD pegawai James Darrell Edwards III menangkap seorang penjenayah yang melarikan diri secara luar biasa tangkas dan melihat matanya berkedip dengan cara yang luar biasa sebelum dia melompat dari bumbung muzium Guggenheim. Semasa soal siasatnya, K tiba dan meninjau James sebagai rakan kongsi baharu yang berpotensi, kagum dengan keupayaannya untuk mengejar makhluk asing. K menerangkan kepada James bahawa organisasi mereka, Men in Black, diasaskan selepas hubungan pertama dibuat dengan alien pada tahun 1961; pada masa ini Bumi telah ditubuhkan sebagai zon neutral politik untuk pelarian asing.

MIB ialah organisasi rahsia yang memantau dan mengawal makhluk asing ini, dan menggunakan neuralyzer untuk memadamkan ingatan sesiapa sahaja yang menyaksikan aktiviti makhluk asing. James bersetuju untuk menyertai dan dia dinamakan semula sebagai Agen J, dan identiti awamnya dipadamkan daripada rekod kerajaan.

Sementara itu, makhluk asing terhempas di bahagian utara New York, dan membunuh seorang petani bernama Edgar dan mula memakai kulitnya sebagai penyamaran. J dan K menyiasat tapak nahas dan mendapati makhluk asing ini adalah "bug", spesies makhluk asing seperti lipas yang sangat berbahaya. Bug itu membunuh dua makhluk asing yang menyamar yang dihantar ke bilik mayat polis yang diawasi oleh koroner Laurel Weaver. J dan K memeriksa mayat dan J dan Laurel secara tidak sengaja membuka satu kepala, mendedahkan makhluk asing yang kecil dan mati dalam kokpit kawalan. Makhluk asing itu memberitahu mereka "Untuk mengelakkan peperangan, galaksi berada di tali pinggang Orion" sebelum mati.

K neuralyzes Laurel, memberitahu J bahawa lelaki ini adalah Rosenberg, Arquillian dan salah satu keluarga diraja mereka. Mereka mempersoalkan seorang pemberi maklumat, Frank the Pug, yang menjelaskan bahawa Rosenberg adalah penjaga galaksi yang merupakan sumber tenaga sub-atom yang berharga; pepijat membunuh Rosenberg untuk memperolehnya supaya pepijat boleh memusnahkan Arquillians. Frank juga memberitahu mereka bahawa galaksi itu berada di Bumi dan sebenarnya sangat kecil. Sebuah kapal perang Arquillian memasuki orbit Bumi, mengeluarkan dua kata kepada MIB untuk memberi galaksi itu kepada mereka.

J menyimpulkan galaksi berada dalam permata pada kolar kucing Rosenberg Orion, oleh itu Rosenberg cuba menyebut "bell", yang berada dalam jagaan Laurel sekarang. Bug telah membuat potongan yang sama dan tiba di bilik mayat dahulu, dan mengambil galaksi dan melarikan diri bersama Laurel, menelan galaksi. Arquillians, yang sanggup memusnahkan galaksi daripada membiarkan bug memilikinya, memberi amaran kepada MIB bahawa mereka mempunyai satu jam untuk memulihkan galaksi atau mereka akan memusnahkan Bumi.

Dengan semua pengangkutan lain dikunci, J menyedari satu-satunya bug yang melarikan diri ialah ke menara pemerhatian New York State Pavilion di Flushing Meadows, yang dibina untuk 1964 New York World's Fair untuk menyamar dua piring terbang. Bug cuba untuk berlepas tetapi J dan K menembak jatuh kapal itu, dan pepijat itu melepaskan kulit Edgar dan mendedahkan bentuk sebenar. Ia menelan senapang J dan K, dan K menghasutnya untuk menelannya juga. Bug mula menaiki kapal kedua dan J memijak lipas dari tong sampah untuk memusuhinya, terhenti sehingga K menjumpai pistolnya di dalam perutnya dan menembaknya dari dalam. Sisa pepijat menyerang kedua-duanya, tetapi Laurel memusnahkannya dengan pistol J.

Dengan galaksi selamat, K mengakui kepada J bahawa dia tidak melatih rakan kongsi, tetapi pengganti; dia sudah bersedia untuk bersara. J neuralyze K, mencipta cerita muka depan bahawa dia koma selama tiga puluh lima tahun. Laurel menyertai MIB sebagai rakan kongsi baru J, Ejen L. Sementara itu di alam semesta, Arquillian sedang bermain dengan beberapa permata Galaxy seperti guli.